@InProceedings{PereiraLoreSenn:2005:PrEsMé,
author = "Pereira, Marcos Antonio and Lorena, Luiz Antonio Nogueira and
Senne, Edson Luiz Fran{\c{c}}a",
affiliation = "Instituto Nacional de Pesquisas Espaciais, Laborat{\'o}rio
Associado de Computa{\c{c}}{\~a}o e Matem{\'a}tica Aplicada,
(INPE, LAC) and {Instituto Nacional de Pesquisas Espaciais (INPE)}
and {Universidade Estadual Paulista (UNESP)}",
title = "Uma proposta de estabiliza{\c{c}}{\~a}o do m{\'e}todo de
gera{\c{c}}{\~a}o de colunas aplicada ao problema de
localiza{\c{c}}{\~a}o de m{\'a}xima cobertura",
year = "2005",
organization = "Simp{\'o}sio Brasileiro de Pesquisa Operacional (SBPO), 37.",
keywords = "Localiza{\c{c}}{\~a}o de Facilidades, Gera{\c{c}}{\~a}o de
Colunas, Relaxa{\c{c}}{\~a}o Lagrangeana/Surrogate, Facility
Location, Column Generation, Lagrangean/Surrogate Relaxation.",
abstract = "Este trabalho apresenta uma implementa{\c{c}}{\~a}o do
m{\'e}todo de gera{\c{c}}{\~a}o de colunas para resolver
problemas de localiza{\c{c}}{\~a}o de facilidades baseados no
modelo matem{\'a}tico do problema de p-medianas. A abordagem
tradicional de gera{\c{c}}{\~a}o de colunas {\'e} comparada com
uma nova proposta, onde o crit{\'e}rio de custos relativos
empregado na sele{\c{c}}{\~a}o de colunas {\'e} modificado pelo
multiplicador da relaxa{\c{c}}{\~a}o lagrangeana/surrogate. A
efici{\^e}ncia da nova abordagem foi comprovada por testes
computacionais envolvendo inst{\^a}ncias com dados reais de
problemas de m{\'a}xima cobertura, formulados como problemas de
p-medianas, cuja esparsidade nos vetores de custos e na matriz de
restri{\c{c}}{\~o}es representam grande dificuldade para
m{\'e}todos baseados em gera{\c{c}}{\~a}o de colunas. ABSTRACT:
This work presents a column generation algorithm to solve facility
location problems that are based on the mathematical formulation
of p-median problems. The traditional column generation approach
is compared to a new proposal, where the reduced cost criterion
employed at the column selection is modified by the
lagrangean/surrogate multiplier. The efficiency of the new
approach is tested with real data for maximal covering location
problems, formulated as p-median problems. Computational tests
were conducted and showed the impact of sparsity on column
generation based methods.",
conference-location = "Gramado, RS",
conference-year = "26 - 30 set.",
language = "pt",
targetfile = "pereira_uma proposta.pdf",
urlaccessdate = "21 maio 2024"
}